//给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。 
//
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: head = [-10,-3,0,5,9]
//输出: [0,-3,9,-10,null,5]
//解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
// 
//
// 示例 2: 
//
// 
//输入: head = []
//输出: []
// 
//
// 
//
// 提示: 
//
// 
// head 中的节点数在[0, 2 * 10⁴] 范围内 
// -10⁵ <= Node.val <= 10⁵ 
// 
// Related Topics 树 二叉搜索树 链表 分治 二叉树 👍 767 👎 0


package com.cjl.leetcode.editor.cn;

/**
 * [P109]_有序链表转换二叉搜索树
 *
 * @author cjl
 * @date 2022-10-07 22:43:12
 */
public class P109_ConvertSortedListToBinarySearchTree {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P109_ConvertSortedListToBinarySearchTree().new Solution();
        ListNode l1 = new ListNode(1);
        solution.sortedListToBST(l1);
    }
    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        /**
         * 找根节点，区分左右两棵树，递归分治
         * 左闭右开；
         * 双指针查找中间根节点
         *
         * @param head
         * @return
         */
        public TreeNode sortedListToBST(ListNode head) {
            return sortedToBST(head, null);
        }

        public TreeNode sortedToBST(ListNode head, ListNode end) {
            if (head == null || head.equals(end)) {
                return null;
            }
            TreeNode treeNode = new TreeNode();
            ListNode currNode = getMiddleNode(head, end);
            treeNode.val = currNode.val;
            treeNode.left = sortedToBST(head, currNode);
            treeNode.right = sortedToBST(currNode.next, end);
            return treeNode;
        }

        /**
         * 左闭右开
         *
         * @param head
         * @param end
         * @return
         */
        public ListNode getMiddleNode(ListNode head, ListNode end) {
            ListNode slow = head;
            ListNode fast = head;
            while (end != fast && end != fast.next) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}